package com.wfm.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * 单词搜索
 * 2025-02-26 17:22:58
 */
class WordSearch {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean exist(char[][] board, String word) {

            // 这个只是优化，不要也行
            if(!canFormWord(board, word)) return false;

            int h = board.length, w = board[0].length;
            boolean[][] visited = new boolean[h][w];
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    boolean flag = check(board, visited, i, j, word, 0);
                    if (flag) {
                        return true;
                    }
                }
            }
            return false;
        }
        // 从(i,j)开始，判断是否能找到word[k...]
        public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
            if (board[i][j] != s.charAt(k)) {
                return false;
            } else if (k == s.length() - 1) {
                return true;
            }
            visited[i][j] = true;
            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            boolean result = false;
            for (int[] dir : directions) {
                int newi = i + dir[0], newj = j + dir[1];
                if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                    if (!visited[newi][newj]) {
                        boolean flag = check(board, visited, newi, newj, s, k + 1);
                        if (flag) {
                            result = true;
                            break;
                        }
                    }
                }
            }
            visited[i][j] = false;
            return result;
        }

        public boolean canFormWord(char[][] board, String word) {
            // 优化1 统计board的单词数量
            // Step 1: 统计 board 中所有字符的频率
            Map<Character, Integer> cnt = new HashMap<>();
            for (char[] row : board) {
                for (char c : row) {
                    cnt.put(c, cnt.getOrDefault(c, 0) + 1);
                }
            }

            // Step 2: 统计 word 中所有字符的频率
            Map<Character, Integer> wordCnt = new HashMap<>();
            for (char c : word.toCharArray()) {
                wordCnt.put(c, wordCnt.getOrDefault(c, 0) + 1);
            }

            // Step 3: 检查 board 是否包含 word 所需的所有字符（优化一）
            for (Map.Entry<Character, Integer> entry : wordCnt.entrySet()) {
                char key = entry.getKey();
                int requiredCount = entry.getValue();
                if (cnt.getOrDefault(key, 0) < requiredCount) {
                    return false; // 如果 board 中某个字符的频率不足，直接返回 false
                }
            }

            // 优化二：检查 word 首尾字符的频率
            // Step 4: 比较 word 首尾字符的频率（优化二）
            char firstChar = word.charAt(0);
            char lastChar = word.charAt(word.length() - 1);

            int firstCharCount = cnt.getOrDefault(firstChar, 0);
            int lastCharCount = cnt.getOrDefault(lastChar, 0);

            if (lastCharCount < firstCharCount) {
                // 如果尾字符频率小于首字符频率，反转 word
                word = new StringBuilder(word).reverse().toString();
            }

            // 返回 true 表示通过初步检查
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new WordSearch().new Solution();
        
    }
}